import javax.swing.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-09-27
 * Time: 8:40
 */
public class Test {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);
        tree.remove(4);
        boolean f=tree.search(4);
        System.out.println(f);
    }

    public static class BinarySearchTree {
        class TreeNode {
            public int key;
            public TreeNode left;
            public TreeNode right;

            TreeNode(int key) {
                this.key = key;
            }
        }

        public TreeNode root;

        /**
         * 插入一个元素
         *
         * @param key
         */
        public void insert(int key) {
            if (root == null) {
                root = new TreeNode(key);
                return;
            }
            TreeNode current = root;
            TreeNode parent = null;
            while (current != null) {
                parent = current;
                if (key < current.key) {
                    current = current.left;
                    if (current == null) {
                        parent.left = new TreeNode(key);
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = new TreeNode(key);
                        return;
                    }
                }
            }
        }


        //查找key是否存在
        public boolean search(int key) {
            TreeNode cur=root;
            while (cur != null) {
                if (key == cur.key) {
                    return true;
                } else if (key < cur.key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
            return false;
        }

        //删除key的值
        public void remove(int key) {
            TreeNode cur = root;
            TreeNode p = null;
            while (cur.key != key) {
                p = cur;
                if (cur.key < key) {
                    cur = cur.right;
                } else {
                    cur = cur.left;
                }
            }
            if(cur==null){
                return;
            }
            //左树为空
            if (cur.left == null) {
                if (cur == root) root = cur.right;
                else {
                    if (cur == p.left) {
                        p.left = cur.right;
                    } else {
                        p.right = cur.right;
                    }
                }
            } else if (cur.right == null) {//右树为空
                if (cur == root) root = cur.left;
                else {
                    if (cur == p.left) {
                        p.left = cur.left;
                    } else {
                        cur.right = cur.left;
                    }
                }
            } else {//都不为空
                TreeNode minNode = cur.right;
                TreeNode minNodeParent = cur;
                while (minNode.left != null) {
                    minNodeParent = minNode;
                    minNode = minNode.left;
                }

                // 替换当前节点的值
                cur.key = minNode.key;

                // 移除右子树中的最小节点
                if (minNodeParent.left == minNode) {
                    minNodeParent.left = null;
                }
            }
        }
    }
}
